package leetcode.tree;

public class DiameterOfBinaryTree543 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution1 {
        int ans = 0;
        public int diameterOfBinaryTree(TreeNode root) {
            deepth(root);
            return ans - 1;
        }

        public int deepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int l = deepth(root.left);
            int r = deepth(root.right);
            ans = Math.max(ans, l + r + 1);
            return Math.max(l, r) + 1;
        }
    }

    class Solution2 {
        int ans = 0;
        public int diameterOfBinaryTree(TreeNode root) {
            deepth(root);
            return ans;
        }

        public int deepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = deepth(root.left);
            int right = deepth(root.right);
            ans = Math.max(ans, left + right);
            return Math.max(left, right) + 1;
        }
    }
}
